package datastruct.set;

import java.util.Arrays;

/**
    * @author wangc
    * 带秩的并查集，秩即为到根节点的距离
    * @date 2021/6/15 下午 8:52
*/
public class RankUnionSet {

    int[] parent, rank;

    public RankUnionSet(int n) {
        parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
        rank = new int[n];
        Arrays.fill(rank,1);
    }

    public int findRoot(int x){
        if(x==parent[x]) return x;
        return findRoot(parent[x]);
    }

    //按秩合并，秩小集合并到秩大集合上
    public int merge(int x, int y){
        int res = 0;
        int xRoot = findRoot(x);
        int yRoot = findRoot(y);
        if(rank[xRoot]>rank[yRoot]){
            parent[yRoot] = xRoot;
            res = xRoot;
        }else if(rank[xRoot]<rank[yRoot]) {
            parent[xRoot] = yRoot;
            res = yRoot;
        }else {
            parent[xRoot] = yRoot;
            res = yRoot;
            rank[yRoot]++;
        }
        return res;
    }
}
